package 剑指Offer1;

public class _26链表中倒数第k个节点 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) return null;
        int size = size(head);
        if(size == k) return head; //链表节点个数和需要返回的倒数第K个节点数一致，返回头节点即可
        ListNode fast = head,slow = head;
        for(int i=1;i<=k;++i){ //快指针先走K步
            fast = fast.next;
        }
        //快指针走到链表尾部相当于走了整个链表的长度，而慢指针则走了size - k的长度，刚好到达倒数第K个节点
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;

    }

    private int size(ListNode head){
        ListNode tmp = head;
        int size = 0;
        while(tmp!=null){
            size++;
            tmp = tmp.next;
        }
        return size;
    }
}
